package leetcode.dfs;

import java.util.LinkedList;
import java.util.Queue;

//542. 01 矩阵
public class UpdateMatrix {
    public static void main(String[] args) {

    }

    //BFS
    public static int[][] updateMatrix(int[][] mat) {
        Queue<int[]> queue = new LinkedList<>();

        // 首先将所有的 0 都入队，并且将 1 的位置设置成 -1，表示该位置是 未被访问过的 1
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                } else {
                    mat[i][j] = -1;
                }
            }
        }
        int[] dx = new int[]{-1, 1, 0, 0};
        int[] dy = new int[]{0, 0, -1, 1};
        while (!queue.isEmpty()) {
            int[] point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int mx = point[0] + dx[i];
                int my = point[1] + dy[i];
                if (mx >= 0 && mx < mat.length && my >= 0 && my < mat[0].length && mat[mx][my] == -1) {
                    mat[mx][my] = mat[point[0]][point[1]] + 1;
                    queue.offer(new int[]{mx, my});
                }
            }
        }
        return mat;
    }

    /**
     * 本题还有一种 BFS 的做法，就是先找出在 00 边上的所有的 11，然后把这些 11 放到队列里，后续BFS的时候就只关心 11 的值。
     *
     * @param mat
     * @return
     */
    public static int[][] updateMatrix2(int[][] mat) {
        // 首先将 0 边上的 1 入队
        int[] dx = new int[]{-1, 1, 0, 0};
        int[] dy = new int[]{0, 0, -1, 1};
        Queue<int[]> queue = new LinkedList<>();
        int m = mat.length, n = mat[0].length;
        int[][] flag = new int[m][n];  //作为标志，默认为0
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //如果改位置是0，则让其旁边的所有1入队
                if (mat[i][j] == 0) {
                    for (int k = 0; k < 4; k++) {
                        int mx = i + dx[k];
                        int my = j + dy[k];
                        if (mx >= 0 && mx < m && my >= 0 && my < n && mat[mx][my] == 1 && flag[mx][my] == 0) {
                            flag[mx][my] = 1;
                            queue.offer(new int[]{mx, my});
                        }
                    }
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] point = queue.poll();
            int x = point[0], y = point[1];
            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i];
                int newY = y + dy[i];
                if (newX >= 0 && newX < m && newY >= 0 && newY < n
                        && mat[newX][newY] == 1 && flag[newX][newY] == 0) {
                    flag[newX][newY] = flag[x][y] + 1;
                    queue.offer(new int[]{newX, newY});
                }

            }

        }
        return flag;

    }


    //动态规划
    public static int[][] updateMatrix3(int[][] mat) {

        int m = mat.length, n = mat[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = mat[i][j] == 0 ? 0 : 10000;
            }
        }

        //左上
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (j - 1 >= 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
                }
                if (i - 1 >= 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
                }
            }
        }

//            //右上
//            for (int i = 0; i < m; i++) {
//                for (int j = 0; j < n; j++) {
//                    if (i - 1 >=0) {
//                        dp[i][j] = Math.min(dp[i][j], dp[i -1][j] + 1);
//                    }
//                    if (j + 1 < n) {
//                        dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
//                    }
//                }
//            }
//
//            //左下
//            for (int i = 0; i < m; i++) {
//                for (int j = 0; j < n; j++) {
//                    if (i + 1 < m) {
//                        dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
//                    }
//                    if (j - 1 >= 0) {
//                        dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
//                    }
//                }
//            }

        //右下
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (j + 1 < n) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
                }
                if (i + 1 < m) {
                    dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
                }

            }
        }
        return dp;
    }


}
